
/*
 * Question: Suppose that a complete binary tree is stored
 * in a sequential table 'sa'. Try to propose an algorithm
 * to create a binary tree linked list in terms of the
 * sequential table.
 *
 * Date: 01/26/2012
 */

#include <iostream>
#include <vector>
#include <queue>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree,char>
{
};

void create(vector<char> sa, bitree *&rt)
{
    queue<bitree *> q;
    bitree *p;
    int i;

    bitree_init(rt);
    if (sa.size() <= 0)
        return;
    rt = new bitree;
    rt->key = sa[1];
    q.push(rt);
    i = 1;
    while (!q.empty()){
        p = q.front(); q.pop();
        if (sa[i*2] != '#'){
            p->lchild = new bitree;
            p->lchild->key = sa[i*2];
            q.push(p->lchild);
        }
        else
            p->lchild = NULL;
        if (sa[i*2+1] != '#'){
            p->rchild = new bitree;
            p->rchild->key = sa[i*2+1];
            q.push(p->rchild);
        }
        else
            p->rchild = NULL;
        i++;
    }
}

int main()
{
    bitree *rt;
	vector<char> sa;
	ifstream input("ex54.txt");
	int n;
	input >> n;
	for (int i = 0; i <= n; i++){
		char c;
		input >> c;
		sa.push_back(c);
	}
    create(sa, rt);
    bitree_print(rt);
    bitree_destory(rt);

    return 0;
}
